package leetcode.code046.Permutations;

import java.util.ArrayList;
import java.util.List;

public class Solution04602 extends Permutations {

	@Override
	public List<List<Integer>> permute(int[] nums) {
		int len = nums.length;
		boolean[] avilable = new boolean[len];
		for (int i = 0; i < len; i++) {
			avilable[i] = true;
		}
		return this.permute1(nums, avilable);
	}

	public List<List<Integer>> permute1(int[] nums, boolean[] avilable) {
		List<List<Integer>> result = new ArrayList<>();
		for (int i = 0; i < avilable.length; i++) {
			if (avilable[i]) {
				Integer num = nums[i];
				avilable[i] = false;
				List<List<Integer>> sub = this.permute1(nums, avilable);
				if (sub.size() > 0) {
					for (List<Integer> l : sub) {
						l.add(0, num);
						result.add(l);
					}
				} else {
					List<Integer> temp = new ArrayList<>();
					temp.add(num);
					result.add(temp);
				}
				avilable[i] = true;
			}
		}
		return result;
	}

//	public List<List<Integer>> permute1(List<Integer> nums) {
//		List<List<Integer>> result = new ArrayList<List<Integer>>();
//		for (Integer num : nums) {
//			nums.remove(num);
//			List<List<Integer>> sub = this.permute1(nums);
//			for(List<Integer> l : sub) {
//				nums.add(num);
//			}
//			result.addAll(sub);
//			nums.add(num);
//		}
//		return result;
//	}

	public static void main(String[] args) {
		Solution04602 so = new Solution04602();
		so.debug1();
//		so.debug2();
//		so.debug3();
	}
}
